/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "atomic.h"
#include "mem_barrier.h"
#include "rcu.h"
#include <stdio.h>

using namespace nbds;

rcu_rc_base::rcu_rc_base(void *p, void (*d)(void*), void *(*c)(void*)) :
		delete_obj(d), copy_obj(c) {
	ptr_cell *cell = new ptr_cell;
	cell->obj = p;
	cell->counter = 1;

	cells.push_front(cell);
	current_cell = cell;
}

rcu_ptr_base rcu_rc_base::lock_write_() {
	ptr_cell *read;

	do {
		read = arch::get(&current_cell);
		if (arch::ftch_and_add(&read->counter, 1) == 1)
			continue;
	} while (!read->obj);

	return rcu_ptr_base(copy_obj(read->obj), (void*)read);
}

rcu_ptr_base rcu_rc_base::lock_read_() {
	ptr_cell *read;

	do {
		read = arch::get(&current_cell);
		if (arch::ftch_and_add(&read->counter, 1) == 1)
			continue;
	} while (!read->obj);

	return rcu_ptr_base(read->obj, (void*)read);
}

bool rcu_rc_base::release_write_(rcu_ptr_base &obj) {
	list<ptr_cell*>::iterator it = cells.begin();
	ptr_cell *ncell = NULL;
	while (!it.did_cycle()) {
		if (arch::cmp_and_swp(&(*it)->obj, (void*)0, obj.mobj)
								== NULL) {
			ncell = *it;
			ncell->counter = 1;
			break;
		}

		it++;
	}
	if (!ncell) {
		ncell = new ptr_cell;
		ncell->obj = obj.mobj;
		ncell->counter = 1;
		cells.push_front(ncell);
	}

	bool result = arch::cmp_and_swp(&current_cell,
			(ptr_cell*)obj.cobj, ncell) == (ptr_cell*)obj.cobj;

	ptr_cell *prev = (ptr_cell*)obj.cobj;
	void *pobj = prev->obj;

	if (!result) {
		if (arch::ftch_and_add(&ncell->counter, -1) == 1) {
			ncell->obj = 0;
			delete_obj(obj.mobj);
		}	
		
		if (arch::ftch_and_add(&prev->counter, -1) == 1) {
			prev->obj = 0;
			delete_obj(pobj);
		}
	} else {
		if (arch::ftch_and_add(&prev->counter, -2) == 2) {
			prev->obj = 0;
			delete_obj(pobj);
		}
	}

	return result;
}

void rcu_rc_base::release_read_(const rcu_ptr_base &obj) {
	ptr_cell *cell = (ptr_cell*)obj.cobj;
	if (arch::ftch_and_add(&cell->counter, -1) == 1) {
		cell->obj = 0;
		delete_obj(obj.mobj);
	}
}

rcu_ticket_base::rcu_ticket_base(rcu_hp_base *b, void **hp) :
	base(b), hazard_pointer(hp) { }

rcu_ticket_base::rcu_ticket_base(const rcu_ticket_base &x) :
	base(x.base), hazard_pointer(x.hazard_pointer) { }

void rcu_ticket_base::release() {
	base->release_ticket_(hazard_pointer);
}

rcu_ptr_base rcu_ticket_base::lock_write_() {
	void *obj;

	do {
		obj = arch::get(&base->obj);
		arch::set(hazard_pointer, obj);
	} while (obj != arch::get(&base->obj));

	void *mobj = base->copy_obj(obj);
	arch::set(hazard_pointer, (void*)0);

	return rcu_ptr_base(mobj, obj);
}

rcu_ptr_base rcu_ticket_base::lock_read_() {
	void *obj;

	do {
		obj = arch::get(&base->obj);
		arch::set(hazard_pointer, obj);
	} while (obj != arch::get(&base->obj));

	return rcu_ptr_base(obj, (void*)0);
}

bool rcu_ticket_base::release_write_(rcu_ptr_base &obj) {
	bool result = arch::cmp_and_swp(&base->obj, obj.cobj, obj.mobj)
								== obj.cobj;
	if (!result) {
		base->delete_obj(obj.mobj);
		return false;
	}

	retired.push_back(obj.cobj);

	std::list<void*>::iterator it = retired.begin();
	while (it != retired.end()) {
		list<void*>::iterator hpit = base->hzrd_ptrs.begin();
		while (!hpit.did_cycle()) {
			if (*hpit == *it)
				break;
			hpit++;
		}

		if (*hpit == *it) {
			it++;
		} else {
			base->delete_obj(*it);
			it = retired.erase(it);
		}
	}

	return true;
}

void rcu_ticket_base::release_read_(const rcu_ptr_base &obj) {
	*hazard_pointer = (void*)0;
}

rcu_hp_base::rcu_hp_base(void *p, void (*del)(void*), void *(*cpy)(void*)) :
	obj(p), delete_obj(del), copy_obj(cpy) { }

void **rcu_hp_base::get_ticket_() {
	void **hp = free_hps.pop();
	if (hp)
		return hp;

	hp = new void*;
	*hp = (void*)0;
	hzrd_ptrs.push_front(hp);

	return hp;
}

void rcu_hp_base::release_ticket_(void **hp) {
	free_hps.push(hp);
}
